// https://leetcode.cn/problems/jump-game/

/*
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

思路：只要有一个格可以跳到，则代表可以跳到
*/
#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    bool canJump(vector<int>& nums) {
		int len = nums.size();
		if(len > 1 && nums[0] == 0){
			return false;
		}
		
		int maxStep = 1;
		for(int i = 0; i < len; i++){
			maxStep = max(maxStep, i + nums[i]);
			if(maxStep <= i){
				return false;
			}
			if(maxStep >= len - 1){
				return true;
			}
		}
		
		return true;
    }
	
	// 优化代码
	bool canJump1(vector<int>& nums) {
		int maxStep = 0;
		int len = nums.size();
		for(int i = 0; i < len;  i++){
			maxStep = max(maxStep, i + nums[i]);
			
			if(maxStep >= len - 1){
				return true;
			}
			if(maxStep <= i){
				return false;
			}
		}
		return true;
    }
};

int main(){
	Solution so;
	vector<int> s1 = {3, 2, 1, 0, 4};
	bool a = so.canJump1(s1);
	cout << a << endl;
	return 0;
}